//双向链表
public class MyLinkedList {
    static class ListNode{
        public int val;
        public ListNode pre;
        public ListNode next;
        //内部类里面得提供一个构造方法

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;




    public  boolean contains(int key){
        ListNode cur=head;
        while (cur.next!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    public void remove(int key){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val == key) {
                //开始删除
                if (cur==head){

                    head=head.next;//虽然我们已经把头尾都考虑进去了，
                    // 但是如果只有**一个节点，head=last=cur，head和last都是null（空指针异常
                    if(head!=null){
                    head.pre=null;
                    }else{
                        last=null;//else里面此时head已经为null了
                    }
                }else if (cur==last){
                    last=last.pre;
                    last.next=null;;
                }else {
                    cur.pre.next=cur.next;//必须把头和尾分别讨论，否则在41，42行会空指针异常
                    cur.next.pre=cur.pre;
                }
                return;//删一个删完就走
            }
            cur=cur.next;
        }
    }
    public  int size(){
        int count=0;
        ListNode cur=head;
        while (cur.next!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public  void addFirst(int data){
        ListNode node=new ListNode(data);
        if (head==null){
            head=last=node;

        }else {
            node.next=head;
            head.pre=node;
            head=node;

        }
    }
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(last==null){
            head=last=node;
        }else {
            last.next=node;
            node.pre=last;
            last=node;
        }
    }
    //需要检测index的合法性
    public void addIndex(int index,int data){
        try {
            checkIndex(index);
        }catch (IndexNotLegalException e){
            e.printStackTrace();
        }
        if (index==0){
            addFirst(data);
            return;
        }
        if (index==size()){
            addLast(data);
            return;
        }
        //处理中间位置，第一步要找到要插入的位置
        ListNode cur=findIndex(index);
        ListNode node=new ListNode(data);
        //插入
        node.pre=cur.pre;
        node.next=cur;
        node.pre.next=node;//顺序不固定，能连上就行
        cur.pre=node;

    }
    private void checkIndex(int index){
        if (index<0||index>size()){
            throw new IndexNotLegalException("双向链表插入index位置不合法"+index);
        }
    }
private ListNode findIndex(int index){
        ListNode cur=head;
        while (index!=0){
            cur=cur.next;
            index--;
        }
        return cur;
}
public void clear(){
        ListNode cur=head;
        while (cur!=null){
            ListNode curN=cur.next;
            cur.pre=null;
            cur.next=null;
            cur=curN;
        }
        head=last=null;
}

}